package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 基本计数排序:要求所有元素大于等于0并且最大值不能太大
 * @version: 1.0
 */
public class CountSort {
    /*
      1.找到最大值，创建一个大小为 最大值+1 的count数组
      2.count数组的索引对应的元素，用来统计该元素出现的次数
      3.遍历count数组，根据count数组的索引以及出现的次数生成排序后的内容
         count数组的索引:已经排好序了

     * 时间复杂度: O(nlogn)  O(n^2) O(nlogn)
     * 空间复杂度: O(logn)
     */
    public static int[] countSort(int[] arr) {
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        //统计每个元素出现的次数
        int[] count = new int[maxNum + 1];
        for (int i : arr) {
            count[i]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            //i:原始数组的值  arr[i]:出现的次数
            while (count[i] > 0) {
                arr[k] = i;
                count[i]--;
                k++;
            }
        }
        return arr;
    }
}
